Introduction to Machine Learning

Unit 23: NN Python Demo + Agglomerative Clustering

1. Introduction

This unit brings together two important topics in machine learning. First, we wrap up our discussion on Neural Networks with a practical Python demonstration on the Diabetes dataset, exploring various hyperparameters and regularization techniques. Second, we introduce the vast field of Clustering, specifically focusing on hierarchical approaches with Agglomerative Clustering and its linkage methods: single, complete, and average.

Learning Objectives

Today's Agenda

  1. Recap of the Previous Lecture
  2. Discussion on Challenge 2
  3. Neural Network Summary
  4. Python Demo of Hyperparameters of NN
  5. Introduction to Clustering
  6. Partitional vs Hierarchical Clustering
  7. Agglomerative Clustering
  8. Simple, Complete and Average Linkages

2. Theory

2.1 Neural Networks: Advantages and Disadvantages

Neural networks are powerful models but come with important tradeoffs. The most prominent advantage is their good predictive performance. They are known to have high tolerance to noisy data and the ability to capture highly complicated non-linear relationships between predictors and an outcome variable.

Their weakest point is in providing insight into the structure of the relationship, hence their blackbox reputation. Several considerations and dangers should be kept in mind when using neural networks:

Advantages
Disadvantages / Risks
Key Considerations

2.2 NN Training Summary (7-Step Workflow)

  1. Select the architecture: Number of layers, their sizes, and the type of activation function.
  2. Initialize weights and biases: Use intelligently selected initial values (e.g., He, Glorot).
  3. Forward pass minibatch: Run a minibatch through the network and compute the mean loss.
  4. Backpropagation: Calculate the contribution of each weight and bias to the overall loss for the minibatch.
  5. Gradient descent update: Update the weight and bias values of the model based on the contributions.
  6. Repeat: Continue from step 3 until desired epochs, threshold loss, or validation convergence.
  7. Regularize if needed: Apply L1/L2, dropout, early stopping, or data augmentation if the network isn't learning well.

2.3 Python Demo: Diabetes Dataset

The demo uses the Diabetes health indicator dataset from UCI ML Repository containing 21 columns and tens of thousands of records. Predictors include HighBP, HighChol, Stroke, Smoking, Fruits, Veges, Age, Sex, BMI, Education, Income, etc. The target has two categories: 0 for no diabetes, 1 for pre-diabetes or diabetes.

Data Preparation

Diabetes Health Indicator Dataset Preparation and Split A visual summary of the Diabetes Health Indicator UCI dataset, its feature scaling, train-test split, and class distributions. Diabetes Health Indicator Dataset Data preparation and class-balanced evaluation split Dataset Overview Diabetes Health Indicator (UCI) Predictive health indicators for diabetes classification FEATURES 21 predictor features + 1 binary target INPUT DATA X → StandardScaler() Scaling applied to predictors PARTITION 70% Train 30% Test · random_state=2 1 Standardize predictors Apply StandardScaler() to X Normalize feature magnitudes before modeling 2 Stratified data split 70% Train · 30% Test Train Set 70% · 177,576 Class 1 · diabetes 24,659 records Class 0 · no diabetes 152,917 records TOTAL TRAINING RECORDS 177,576 Test Set 30% · 76,104 Class 1 · diabetes 10,687 records Class 0 · no diabetes 65,417 records TOTAL TEST RECORDS 76,104

Pass 1: Baseline Model (Adam Optimizer)

Architecture & Results

Pass 2: Changing Optimizer (SGD with Momentum)

SGD Configuration

Pass 3: Early Stopping Callback

EarlyStopping Setup

Pass 4: Adding Dropout Regularization

Dropout Architecture

Pass 5: Simpler Architecture

Question:

Dense(20, relu, input_dim=21) + Dropout(0.25) + Dense(1, sigmoid). How many parameters in this architecture?

Reveal Answer
  • Layer 1: (21 inputs × 20 neurons) + 20 biases = 440 parameters
  • Output Layer: (20 inputs × 1 neuron) + 1 bias = 21 parameters
  • Total: 461 parameters

Result with early stopping on val_loss: [loss=0.3150, AUC=0.8287]

Pass 6: L1 and L2 Regularization

Weight Regularization

Pass 7: He-Normal Weight Initialization

He Normal + Validation Split

Comparison with Ensemble Models

Model Name Time (sec) AUC
LGBM0.5400.8297
Cat Boost1.7990.8289
XGB1.4680.8296
MLP (sklearn, 10 epochs)5.9000.8279

2.4 Introduction to Clustering

Cluster Analysis is about finding similarities between data and grouping similar data objects into clusters. It is an unsupervised learning method: no predefined classes are used. A canonical example is Google News grouping similar news stories.

Clustering Objective A visual explanation of clustering, showing maximized distances between clusters and minimized distances among points within each cluster. MACHINE LEARNING CONCEPT Clustering Objective Inter-cluster distances are maximized Clusters are well-separated from one another MAXIMIZED Cluster A Cluster C Cluster B Intra-cluster distances are minimized Points within the same cluster stay close together CLOSE

2.5 The Notion of a Cluster Can Be Ambiguous

Depending on your viewpoint, the same dataset could have 4 clusters, 2 clusters, or 6 clusters. The "right" answer depends on context and application. This is one reason clustering evaluation is subtle.

2.6 Two Major Clustering Paradigms

Partitional Clustering
Hierarchical Clustering
Partitional clustering diagram Original points are separated into three non-overlapping clusters. Partitional Clustering Assigning each point to exactly one cluster Original Points PARTITION A Partitional Clustering C1 C2 C3 K = 3 clusters non-overlapping
Dendrogram hierarchical clustering A hierarchical clustering dendrogram showing all data divided into three clusters, each containing two points. A cut at the indicated level produces three clusters. Dendrogram Hierarchical clustering structure Cut higher → K=1 All Data Cluster A Cluster B Cluster C Cut here → K=3 clusters p1 p2 p3 p4 p5 p6 Horizontal cut determines the number of clusters Hierarchical clustering • visual representation

Side-by-Side Comparison

Aspect Hierarchical Clustering Partitional Clustering (e.g., K-Means)
Number of Clusters No need to specify in advance Some require K (K-Means, K-Medoids); some discover K (DBSCAN, OPTICS, ART)
Result Dendrogram showing nested clusters Single partition of data
Flexibility Can obtain any number of clusters by cutting dendrogram Fixed K clusters
Dataset Size Best for small to medium datasets (< 10,000 points) Suitable for large datasets (millions of points)
Common Applications Biological taxonomy, document organization, gene sequence analysis, social network analysis Customer segmentation, image compression, document clustering, anomaly detection
Deterministic? Yes — same data gives same result Varies: K-Means no, DBSCAN yes

2.7 Types of Hierarchical Clustering

Agglomerative (Bottom-Up)
Divisive (Top-Down)

2.8 Agglomerative Clustering Algorithm

  1. Compute the proximity (distance) matrix between all points.
  2. Let each data point be its own cluster initially.
  3. Repeat:
  4.    a) Merge the two closest clusters.
  5.    b) Update the proximity matrix to reflect distances to the new merged cluster.
  6. Until only a single cluster remains (or k clusters).

The key operation is the computation of the proximity of two clusters. Different approaches to defining this distance distinguish the different Agglomerative algorithms.

Aggregating Clusters: Proximity Matrix A proximity matrix for points p1 through p5. The minimum distance is 0.2 between p1 and p2, indicating that they should be merged. AGGREGATING CLUSTERS Proximity Matrix DISTANCE VALUES p1 p2 p3 p4 p5 p1 p2 p3 p4 p5 0 0.2 0.8 0.9 1.1 0.2 0 0.7 0.85 1.05 0.8 0.7 0 0.3 1.2 0.9 0.85 0.3 0 1.15 1.1 1.05 1.2 1.15 0 STEP 1 Nearest pair found Minimum distance p1 ↔ p2 = 0.2 MERGE Action: merge p1 and p2, then recalculate the proximity matrix.

2.9 Inter-Cluster Similarity: Linkage Methods

Given two clusters \( c_i \) and \( c_j \), how do we compute a single distance \( D(c_i, c_j) \) between them? Four common methods:

Single Linkage (MIN)
Complete Linkage (MAX)
Average Linkage
Centroid Distance

Definition: Distance between clusters = the shortest distance between any two points in different clusters.

\[ D(c_i, c_j) = \min_{\substack{a \in c_i \\ b \in c_j}} d(a, b) \]

When merging \( c_k = c_i \cup c_j \), the Lance-Williams update is:

\[ D(c_k, c_l) = \min\{D(c_i, c_l), D(c_j, c_l)\} \]

Susceptible to chaining — single long bridge can merge whole chains of clusters.

Definition: Distance between clusters = the greatest distance between any two points in different clusters.

\[ D(c_i, c_j) = \max_{\substack{a \in c_i \\ b \in c_j}} d(a, b) \]

Produces compact, tightly-diameter clusters; sensitive to outliers.

Definition: Distance between clusters = the average distance between all pairs of points in different clusters.

\[ D(c_i, c_j) = \frac{1}{|c_i| \cdot |c_j|} \sum_{\substack{a \in c_i \\ b \in c_j}} d(a, b) \]

Update formula for \( c_k = c_i \cup c_j \):

\[ D(c_k, c_l) = \frac{|c_i|}{|c_k|} D(c_i, c_l) + \frac{|c_j|}{|c_k|} D(c_j, c_l) \]

Balanced compromise between single and complete linkage.

Definition: Distance between clusters = Euclidean distance between their cluster centroids (mean vectors).

\[ D(c_i, c_j) = d(\mu_i, \mu_j), \quad \mu = \frac{1}{|c|}\sum_{x \in c} x \]

Simple but can suffer from inversions (merging increases total distance).

Linkage Methods Visualized A visual comparison of single, complete, average, and centroid linkage between two clusters. LINKAGE METHODS VISUALIZED How the distance between two clusters is defined Cluster cᵢ cᵢ = {p₁, p₂, p₃} Cluster cⱼ cⱼ = {p₄, p₅} p₁ p₂ p₃ p₄ p₅ MIN distance · Single Link MAX distance · Complete Link Other pairwise distances 3 × 2 = 6 cross-cluster pairs Average Link Mean of all 3 × 2 pairwise distances d(cᵢ, cⱼ) = mean { d(pₖ, pₗ) } Balances every connection between the clusters Centroid Linkage Distance between the two cluster means d(cᵢ, cⱼ) = d( μᵢ, μⱼ ) μᵢ = mean(p₁,p₂,p₃) · μⱼ = mean(p₄,p₅)

3. Interactive Examples

Example 1: Parameter Counting in a Neural Network

An MLP has: Input dim = 20, Hidden1 = 32 (ReLU), Hidden2 = 16 (ReLU), Output = 3 (softmax). How many trainable parameters are there?

  • Hidden1: (20 × 32) + 32 = 640 + 32 = 672
  • Hidden2: (32 × 16) + 16 = 512 + 16 = 528
  • Output: (16 × 3) + 3 = 48 + 3 = 51
  • Total: 672 + 528 + 51 = 1,251 parameters

Example 2: NN Architecture Interpretation

In Pass 5 we compared Adam vs SGD and observed that:

Which statement is MOST supported by this single comparison?

Reveal Answer

On this specific dataset, with this architecture, Adam achieves a higher test AUC than SGD with momentum 0.9 at lr = 0.01. We cannot generalize this to all datasets or architectures — SGD may outperform Adam on other tasks, especially with tuning.

Example 3: Partitional vs Hierarchical Choice

A startup with 100,000,000 customer records wants to run marketing on customer segments. Which clustering approach is better, and why?

Partitional clustering (K-Means / DBSCAN). Hierarchical clustering has \(O(n^2)\) memory cost for the proximity matrix, which is impossible for 100M points. Partitional methods scale linearly or near-linearly. The flexibility of choosing K post-hoc via dendrogram is not worth the computational infeasibility here.

Example 4: Linkage Intuition

Two clusters are shaped like two long thin crescents that touch at one point. Which linkage method will definitely merge them first?

Reveal Answer

Single Linkage (MIN). Because the touching pair has distance ≈ 0, Single Linkage will merge the crescents even if the majority of points in each crescent are far apart. This is the "chaining effect." Complete Linkage would compute the MAX distance (crescent tip to opposite tip) and keep them separate.

4. Numerical Solutions

Problem 1: Agglomerative Clustering — First Merge

Given 5 points with Euclidean distance matrix:

ABCDE
A037911
B306810
C760212
D982013
E111012130

Which pair is merged first in Single Linkage? What is the merge distance?

📘 Step-by-Step Solution

Step 1. Find the smallest non-zero entry in the matrix.

Off-diagonal values: A-B=3, A-C=7, A-D=9, A-E=11, B-C=6, B-D=8, B-E=10, C-D=2, C-E=12, D-E=13.

Step 2. Minimum value = 2, between C and D.

Step 3. Single Linkage uses min-distance, merge criterion is the smallest entry.

➡️ First merge: {C, D} at distance 2.

Problem 2: Complete Linkage After Merge

After merging C and D from Problem 1 into cluster CD = {C, D}, compute the distance between CD and the other points (A, B, E) using Complete Linkage (MAX).

📘 Step-by-Step Solution

Step 1. D(CD, A) = max(d(C,A), d(D,A)) = max(7, 9) = 9

Step 2. D(CD, B) = max(d(C,B), d(D,B)) = max(6, 8) = 8

Step 3. D(CD, E) = max(d(C,E), d(D,E)) = max(12, 13) = 13

New distances:

CDABE
CD09813
A90311
B83010
E1311100

Next merge will be A-B at distance 3 (Complete Linkage).

Problem 3: Average Linkage Distance

Cluster X = {p1, p2} and Cluster Y = {q1, q2, q3}. The matrix of pairwise Euclidean distances is:

q1q2q3
p1246
p2357

Compute the Average Linkage distance D(X, Y).

📘 Step-by-Step Solution

Step 1. Count pairs: |X| = 2, |Y| = 3, total pairs = 2 × 3 = 6.

Step 2. Sum all pairwise distances:

\[ \sum d(a,b) = 2 + 4 + 6 + 3 + 5 + 7 = 27 \]

Step 3. Divide by number of pairs:

\[ D(X,Y) = \frac{27}{6} = 4.5 \]

➡️ Average Linkage distance = 4.5.

5. Try It Yourself

Practice 1: NN Trainable Parameters

A binary classification MLP takes 15 features as input. The architecture is: Input → Dense(8, relu) → Dense(4, relu) → Dense(1, sigmoid). Compute the total number of trainable parameters.

  • Layer 1: (15 × 8) + 8 = 120 + 8 = 128
  • Layer 2: (8 × 4) + 4 = 32 + 4 = 36
  • Layer 3: (4 × 1) + 1 = 4 + 1 = 5
  • Total = 128 + 36 + 5 = 169 parameters
Practice 2: Dropout Interpretation

A Dropout(0.25) layer follows a Dense(20) layer. Explain:

  1. What does Dropout(0.25) do during training?
  2. What happens during inference (testing)?
  3. Why does Dropout help reduce overfitting?
  1. Training: On each forward pass, each of the 20 units is independently zeroed out with probability 0.25. The remaining 75% of units still receive gradients — effectively training a different "thinned" subnetwork each step.
  2. Inference: Dropout does nothing. All 20 units are active, but their outputs are implicitly scaled (most frameworks handle this at training time by scaling up kept units by 1/0.75, so inference is identity).
  3. Why it helps:
    • Prevents units from co-adapting too strongly to spurious patterns.
    • Forces features to be independently useful — approximates an ensemble of many thinned networks.
Practice 3: Linkage on 3 Points

Three 1-D points at positions: p1 = 0, p2 = 5, p3 = 9. We start with singletons {p1}, {p2}, {p3}.

  1. State the first merge and its distance.
  2. After the first merge, compute the distance from the new cluster to the remaining singleton under: (a) Single Linkage, (b) Complete Linkage, (c) Average Linkage.

1st merge: Pairwise distances: d(p1,p2)=5, d(p2,p3)=4, d(p1,p3)=9. Min is 4 → merge {p2, p3} at distance 4.

Now we have C23 = {p2, p3} and the singleton {p1}. We need D(C23, {p1}):

\[ \text{(a) Single Linkage} = \min(d(p2,p1), d(p3,p1)) = \min(5, 9) = 5 \] \[ \text{(b) Complete Linkage} = \max(d(p2,p1), d(p3,p1)) = \max(5, 9) = 9 \] \[ \text{(c) Average Linkage} = \frac{5 + 9}{2 \cdot 1} = 7 \]

6. Interactive Quiz

Your score: 0 / 5

7. Key Takeaways

  1. Neural networks excel at predictive performance and noise tolerance but are blackboxes with high computational cost, extrapolation risk, and no built-in feature selection.
  2. The 7-step NN workflow: architecture → init → forward pass → backprop → weight update → iterate → regularize.
  3. Regularization for NNs: L1/L2 weight decay, Dropout, Early Stopping, weight initialization (He for ReLU), and data augmentation.
  4. Clustering = unsupervised grouping: maximize inter-cluster distance, minimize intra-cluster distance.
  5. Two paradigms: Partitional (K-Means, DBSCAN — non-overlapping, scalable) vs Hierarchical (dendrogram, nested clusters, best for small/medium data).
  6. Agglomerative HC: start singletons, iteratively merge closest pair using Single (MIN) / Complete (MAX) / Average / Centroid linkage.
  7. Single linkage chains easily; Complete linkage favors compact clusters; Average linkage is a robust middle ground.

8. Common Pitfalls

  1. Scaling before splitting: Always fit StandardScaler/MinMaxScaler on the training split only, then transform both. Fitting on the whole dataset leaks test information and inflates AUC.
  2. Confusing train-batches and test-batch count: With 177,576 train samples and batch 512, batches/epoch = ceil(177,576/512) = 347. Students sometimes divide by test size instead.
  3. Calling EarlyStopping with monitor='val_loss' but no validation_data in model.fit(): the callback cannot see val_loss and silently does nothing.
  4. Applying Agglomerative clustering to 100k+ samples: The proximity matrix is \(O(n^2)\) in memory. Use partitional methods for big data.
  5. Forgetting Lance-Williams updates: After merging two clusters, recompute distances using the correct linkage formula; don't re-evaluate all n² distances (wasteful and can lose the hierarchical property).
  6. Mis-applying MIN formula: Single Linkage between clusters = min over ALL cross pairs, not just the cluster "representatives."

9. Resources